package com.zyk.problem;

import com.zyk.util.ArrayUtil;

import java.util.Arrays;

/**
 * 一个数组中选k个数, 使得他们的与的结果最小
 *
 * @author zhangsan
 * @date 2021/5/16 15:45
 */
public class MinLogicAnd {

    public static int minLogicAnd(int[] arr, int k) {
        return process(arr, 0, k);
    }

    private static int process(int[] arr, int i, int rest) {
        if (i == arr.length) {
            return rest == 0 ? -1 : Integer.MAX_VALUE;
        }
        int p1 = Integer.MAX_VALUE;
        int next = process(arr, i + 1, rest - 1);   // 要这个数
        if (next != Integer.MAX_VALUE) {
            p1 = arr[i] & next;
        }

        int p2 = process(arr, i + 1, rest);     // 不要这个数
        return Math.min(p1, p2);
    }

    public static int dp(int[] arr, int k) {
        int N = arr.length;
        int R = N + 1, C = k + 1;
        int[][] dp = new int[R][C];
        dp[N][0] = -1;
        // 最后一行
        for (int c = 1; c < C; c++) {
            dp[N][c] = Integer.MAX_VALUE;
        }
        // 最左一列, 只依赖下方值
        for (int r = N - 1; r >= 0; r--) {
            dp[r][0] = -1;
        }
        // 从下往上外层, 从左往右内层
        for (int r = N - 1; r >= 0; r--) {
            for (int c = 1; c < C; c++) {
                int p1 = Integer.MAX_VALUE;
                int next = dp[r + 1][c - 1];   // 要这个数
                if (next != Integer.MAX_VALUE) {
                    p1 = arr[r] & next;
                }
                int p2 = dp[r + 1][c];     // 不要这个数
                dp[r][c] = Math.min(p1, p2);
            }
        }
        return dp[0][k];
    }

    // for test
    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            int[] arr = ArrayUtil.generateRandomArray(10, Integer.MAX_VALUE, false, false);
            int k = (int) (Math.random() * arr.length) + 1;
            System.out.println(Arrays.toString(arr));
            System.out.println(k);
            System.out.println(minLogicAnd(arr, k));
            System.out.println(dp(arr, k));
            System.out.println("===============^_^==================");
        }

        /*int times = 10000;
        int maxLen = 10;
        int maxVal = Integer.MAX_VALUE;
        boolean succeed = true;
        System.out.println("测试开始: ");
        for (int i = 0; i < times; i++) {
            int[] arr = ArrayUtil.generateRandomArray(maxLen, maxVal, true, false);
            int k = (int) (Math.random() * arr.length) + 1;
            long s1 = System.currentTimeMillis();
            int ans1 = minLogicAnd(arr, k);
            long s2 = System.currentTimeMillis();
            int ans2 = dp(arr, k);
            long s3 = System.currentTimeMillis();
            if (ans1 != ans2) {
                System.out.println("OOPS");
                System.out.println(Arrays.toString(arr));
                System.out.println(ans1 + "\t" + ans2);
                succeed = false;
                break;
            }
            System.out.println("==========size: " + arr.length + "============");
            System.out.println("全排列: " + (s2 - s1));
            System.out.println("dp: " + (s3 - s2));
            System.out.println("======================");
        }
        System.out.println("finish! success? " + succeed);*/
    }


}
